/* -*-  Mode:C; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1999, 2000 Massachusetts Institute of Technology.
 *
 * This software is being provided by the copyright holders under the GNU
 * General Public License, either version 2 or, at your discretion, any later
 * version. (See the file `LICENSE' in the Linux source distribution.)
 *
 * This software is provided "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. The entire risk as
 * to the quality and performance of the program is with you. See the GNU
 * General Public License for more details.
 *
 * The name and trademarks of copyright holders may NOT be used in 
 * advertising or publicity pertaining to the software without specific, 
 * written prior permission. Title to copyright in this software and any 
 * associated documentation will at all times remain with copyright 
 * holders. See the file CMAUTHORS which should have accompanied this software 
 * for a list of all copyright holders. 
 * 
 * Particular files in this distribution may be derived from previously
 * copyrighted software. This copyright applies only to those changes made by
 * the copyright holders listed in the CMAUTHORS file.
 */
/*
 * An implementation of the Congestion Manager (CM) for Linux.
 * This file implements the CM congestion controller modeled after 
 * TCP.  See RFC 2581 for details on the specific mechanisms.
 */
#include <linux/config.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <net/cm.h>
#include <net/cm_tcpcongctl.h>
#include <linux/wanpipe.h>
#include <net/cm_debug.h>

/*
 * Initialize congestion controller state when a new CM is instantiated 
 * for this destination (macroflow).  Called by cm_open().
 */
void cmtcpcc_init(cm_congctl_t *cmtcpcc)
{
        CM_DPRINTF(CM_DEBUG_FUNCALL|CM_DEBUG_MACROFLOW_INIT,
		   "cm_debug:  %s:  initting CC %p for a new macroflow\n",
		   __FUNCTION__, cmtcpcc);

	cmtcpcc->state.size = cmtcpcc->mflow->mtu;
	cmtcpcc->state.outstanding = 0;	/* nothing sent so far */
	cmtcpcc->state.last_size = 0;
	cmtcpcc->state.last_time = 0;	/* will be set on first xmit */
	cmtcpcc->state.last_loss = 0;
	cmtcpcc->state.srtt = 0;	/* former value: CM_SRTT_DEFAULT */
	cmtcpcc->state.rttmin = 0;
	cmtcpcc->state.rttdev = 0;
	cmtcpcc->state.rto = CM_MAX_RTO;
	cmtcpcc->state.rate = 0;
	cmtcpcc->state.cwnd = cmtcpcc->mflow->mtu;
	cmtcpcc->state.ssthresh = CM_SSTHRESH;
	cmtcpcc->congctl_type = 0;


	cmtcpcc->ops.update = cmtcpcc_update;
	cmtcpcc->ops.query = cmtcpcc_query;
	cmtcpcc->ops.notify = cmtcpcc_notify;
	cmtcpcc->ops.wakeup = cmtcpcc_wakeup;
}

/*
 * Called in first cm_update() call.
 */
inline void cmtcpcc_startup(cm_congctl_t *cmtcpcc, int nrecd, double rtt, 
			 int lossmode)
{
        CM_DEBUG_ENTER();
	if (rtt > 0) {
		cmtcpcc->state.rttmin = cmtcpcc->state.srtt = rtt;
	}
}

/* 
 * Go back into slow start.
 */
inline void cmtcpcc_restart(cm_congctl_t *cmtcpcc, u32 now)
{
	cmtcpcc->state.ssthresh = cmtcpcc->state.cwnd;
	cmtcpcc->state.cwnd = cmtcpcc->state.size; /* 1 packet */
	cmtcpcc->state.last_loss = now;
	CM_DPRINTF(CM_DEBUG_CONGCTL,
		   "TCP_RESTART %d cwnd %d ssthresh %d \n",
		   now, cmtcpcc->state.cwnd, cmtcpcc->state.ssthresh);
	cm_log(CMLOG_RESTART, now, cmtcpcc->state.cwnd, cmtcpcc->state.ssthresh);
}

/*
 * Multiplicative (factor-of-two) reduction in congestion window.
 * Happens at most once per RTT period, to prevent multiple reductions
 * in the same congestion "epoch".
 */
inline void cmtcpcc_decrease(cm_congctl_t *cmtcpcc, u32 now)
{
	if (now - cmtcpcc->state.last_loss 
	    >= (cmtcpcc->state.srtt/10000)) {    /* XXX use rttmin? */
		/* Div by 10,000 to convert to jiffies */
		// cmtcpcc->state.cwnd = 
		// (cmtcpcc->state.outstanding >> CM_DECR_SHIFT);
		cmtcpcc->state.cwnd = 
			(cmtcpcc->state.cwnd >> CM_DECR_SHIFT);
		if (cmtcpcc->state.cwnd < cmtcpcc->state.size)
			cmtcpcc->state.cwnd = cmtcpcc->state.size;
		cmtcpcc->state.ssthresh = cmtcpcc->state.cwnd;
		cmtcpcc->state.last_loss = now;
		CM_DPRINTF(CM_DEBUG_CONGCTL,
			   "TCP_DECREASE %d cwnd %d ssthresh %d \n",
			   now, cmtcpcc->state.cwnd, cmtcpcc->state.ssthresh);
	cm_log(CMLOG_DECREASE, now, cmtcpcc->state.cwnd, cmtcpcc->state.ssthresh);
	} else {
		CM_DPRINTF(CM_DEBUG_CONGCTL_VERBOSE,
			   "Skipped TCP_DECREASE: too soon, now %d last %d srtt %d\n",
			   now, cmtcpcc->state.last_loss,
			   cmtcpcc->state.srtt/10000);
	}
}

/*
 * TCP-style additive-increase.  Some important differences from RFC 2581:
 * (i)  Byte-counting to account for infrequent feedback.
 * (ii) Bursts are avoided by ensuring that sender paces (shapes) packets out.
 *      nrecd is number of successfully received bytes.
 */
inline void cmtcpcc_increase(cm_congctl_t *cmtcpcc, int nrecd)
{
	__u32 now = (__u32)(jiffies);
	if (cmtcpcc->state.cwnd >= cmtcpcc->state.ssthresh) {
			cmtcpcc->state.cwnd += 
				min ((int)((nrecd*cmtcpcc->state.size)/
					   cmtcpcc->state.cwnd), cmtcpcc->state.size); 
	} else {		/* don't jump over ssthresh */
		cmtcpcc->state.cwnd = min(cmtcpcc->state.cwnd + nrecd, 
					  cmtcpcc->state.ssthresh);
	}
	CM_DPRINTF(CM_DEBUG_CONGCTL,
		   "TCP_INCREASE %d cwnd %d ssthresh %d \n",
		   now,cmtcpcc->state.cwnd, cmtcpcc->state.ssthresh);
	cm_log(CMLOG_INCREASE, now, cmtcpcc->state.cwnd, cmtcpcc->state.ssthresh);
}

/* RTO estimation 
 * combined RTO estimation and bounding rto from tcp code
 * do not need two separate 2 line functions
 */

inline void cmtcpcc_update_rto(cm_congctl_t *cmtcpcc) 
{
        cmtcpcc->state.rto = (cmtcpcc->state.srtt >> CM_RTTSHIFT) + cmtcpcc->state.rttdev;
	/* tcp uses snd_cwnd instead of cwnd below; check if this is fine */
        cmtcpcc->state.rto += (cmtcpcc->state.rto >> CM_RTTDEVSHIFT) + (cmtcpcc->state.rto >> (cmtcpcc->state.cwnd-1));
        if (cmtcpcc->state.rto > 120*HZ)
                cmtcpcc->state.rto = 120*HZ;
        if (cmtcpcc->state.rto < HZ/5)
                cmtcpcc->state.rto = HZ/5;
}

/* 
 * Estimate round-trip time.
 */
inline void cmtcpcc_update_rtt(cm_congctl_t *cmtcpcc, u32 rtt)
{
	u32 shrinkage = 0;
	u32 mshrinkage = 0;
	int rtterror = 0;
	
	if (rtt == 0)
		return;
	/* 
	 * Dividing by 8 and multiplying by 7 tends to result in 0 too often.
	 * This is equivalent and subtraction isn't too expensive.
	 */
	shrinkage = cmtcpcc->state.srtt >> CM_RTTSHIFT;
	rtterror = rtt - cmtcpcc->state.srtt;
	cmtcpcc->state.srtt = cmtcpcc->state.srtt - shrinkage;
	cmtcpcc->state.srtt += rtt >> CM_RTTSHIFT;
	if (rtt < cmtcpcc->state.rttmin)
		cmtcpcc->state.rttmin = rtt;
	/* hacked in rttdev calculation too, not checked yet*/
	if (rtterror < 0) rtterror = -rtterror;
	mshrinkage = cmtcpcc->state.rttdev >> CM_RTTDEVSHIFT;
	cmtcpcc->state.rttdev -= mshrinkage;
	cmtcpcc->state.rttdev += rtterror >> CM_RTTDEVSHIFT;
	cmtcpcc_update_rto(cmtcpcc);
}

void cmtcpcc_update(cm_congctl_t *cmtcpcc, int nsent, int nrecd, 
		 u32 rtt, int lossmode)
{
	__u32 now = (__u32)(jiffies);
	int changed = 0;

	if (nsent == 0) 
		return;
	/* not sure if to comment the if block below
	 * Deepak commented it once because no need for this sanity check
	 * since it may not hold even if everything is right
	 * based on situation of updates etc on various flows
	 * but may adding locks onto cm congctl structures makes this 
	 * impossible in which case the sanity check below is useful */
	if (cmtcpcc->state.outstanding < nsent) {
		CM_DPRINTF(CM_DEBUG_USER_ERRS,
			   "cm_debug: user error in cmtcpcc_update: "
			   "nsent %d > outstanding %d\n",
			   nsent, cmtcpcc->state.outstanding);
		nsent = cmtcpcc->state.outstanding;
	}
	CM_DPRINTF(CM_DEBUG_CONGCTL_VERBOSE,
		   "update: outstanding changes from %d to %d \n",
		   cmtcpcc->state.outstanding,
		   cmtcpcc->state.outstanding-nsent);
	cmtcpcc->state.outstanding -= nsent; /* um... what about reordering? */

	if (cmtcpcc->state.srtt == 0 && rtt != 0) /*&& lossmode == CM_NOLOSS)*/
		/* XXX */
		cmtcpcc_startup(cmtcpcc, nrecd, rtt, lossmode);/* slow start */

	/* Assuming no reordering fixes.  Need to modify for reordering. */
	switch (lossmode) {
	case (CM_ECN):
	case (CM_TRANSIENT):
		cmtcpcc_decrease(cmtcpcc, now);
		changed = 1;
		cmtcpcc->state.last_backoff = 0;
		cmtcpcc->state.backoff = 1;
		break;
	case (CM_PERSISTENT):
		cmtcpcc_restart(cmtcpcc, now);
		changed = 1;
		cmtcpcc->state.last_backoff = 0;
		cmtcpcc->state.backoff = 1;
		break;
/*
	case (CM_PARTIALACK):
		Don't do anything for partial acks.
		break;
*/
	default:  /* no losses */
		cmtcpcc_update_rtt(cmtcpcc, rtt);
		/* Commented Deepak: dont know why? */
		/* In last test, commented because wasn't allowing
                 * inc. in many cases */
		/*
		if ((cmtcpcc->state.outstanding + nsent) > 
		    ((cmtcpcc->state.cwnd /2))){
		*/
			cmtcpcc_increase(cmtcpcc, nrecd);
		/*
		}
		*/
		changed = 1;
		cmtcpcc->state.last_backoff = 0;
		cmtcpcc->state.backoff = 1;
		break;
	}

	cmtcpcc_update_rate(cmtcpcc);
}

/*
 * Fill in the bandwidth, srtt and rtt deviation for the macroflow.
 */
void cmtcpcc_query(cm_congctl_t *cmtcpcc, double *bw, double *srtt,
		   double *rttvar)
{

	*bw = cmtcpcc->state.rate;
	*srtt = cmtcpcc->state.srtt;
}

void cmtcpcc_notify(cm_congctl_t *cmtcpcc, int nsent)
{
	__u32 now = (__u32)(jiffies);

	CM_DPRINTF(CM_DEBUG_CONGCTL_VERBOSE,
		   "notify: outstanding changes from %d to %d \n",
		   cmtcpcc->state.outstanding,
		   cmtcpcc->state.outstanding+nsent);
	cmtcpcc->state.outstanding += nsent;
	if ( (cmtcpcc->state.rttmin == 0) ||
	     ((((now - cmtcpcc->state.last_time) * 10000) /* Jiffies->us */
	      * cmtcpcc->state.cwnd / cmtcpcc->state.rttmin)
	     > cmtcpcc->state.last_size)) {
		/* pace is slower than required */
		cmtcpcc->state.last_time = now;
		cmtcpcc->state.last_size = nsent;
	} else {
		/* sent too soon... need to compensate on next send */
		cmtcpcc->state.last_size += nsent;/* so inflate last_size */
	}
}

void cmtcpcc_wakeup(cm_congctl_t *cmtcpcc) {
	cm_sched_t *sched;
#if 0
	__u32 now = (__u32)(jiffies);
#endif
	int pacing_est;
	int maxburst;
	int outstanding;
	sched = cmtcpcc->mflow->sched;
	pacing_est = cmtcpcc->state.size;
	maxburst = CM_TCPCC_MAXBURST;
	outstanding = cmtcpcc->state.outstanding;

#if 0
	if (cmtcpcc->state.rttmin != 0) {
		pacing_est = (cmtcpcc->state.cwnd * 
			      (now - cmtcpcc->state.last_time + 1)) / 
			cmtcpcc->state.rttmin;
		if (pacing_est < cmtcpcc->state.last_size)
			/* too soon for pacing */
			return;
		pacing_est -= cmtcpcc->state.last_size;
	} 
#endif
	while (/* (pacing_est >= cmtcpcc->state.size) && */
	       ((cmtcpcc->state.cwnd >= outstanding + cmtcpcc->state.size)) &&
	       (maxburst-- > 0)) {
		/* give up the lock here since callbacks from the
		   scheduler may need to get the lock */
		spin_unlock_bh(&(cmtcpcc->ccstate_lock));
		/* send a pkt */
		cms_schedule(sched);
		spin_lock_bh(&(cmtcpcc->ccstate_lock));
		pacing_est -= cmtcpcc->state.size;
		outstanding += cmtcpcc->state.size;
	}

}

/* 
 * Compute rate on mflow --- either cwnd or srtt has changed.
 * Then check each flow on the mflow:
 * - if rate callback bounded by thresholds, check them and do callback;
 * - if there aren't any thresholds, do the callback anyway.
 */
void cmtcpcc_update_rate(cm_congctl_t *cmtcpcc)
{
        cm_macroflow_t *mflow = cmtcpcc->mflow;
	int nonzero_srtt = cmtcpcc->state.srtt;
	cm_flow_t *flow;
	double newrate, newfrate;
	int irate;
	if (cmtcpcc->state.srtt == 0) nonzero_srtt = CM_RTT_DEFAULT;
#ifdef CM_AGING
	cmtcpcc->state.rate = (double) cmtcpcc->state.cwnd/
		(nonzero_srtt * cmtcpcc->state.backoff);
#else
	cmtcpcc->state.rate = (double) cmtcpcc->state.cwnd/nonzero_srtt;
#endif
	irate = cmtcpcc->state.rate;
	CM_DPRINTF(CM_DEBUG_CONGCTL,
		   "mflow rate = %d cwnd %d srtt %d\n",
		   irate, cmtcpcc->state.cwnd, nonzero_srtt);
	newrate = cmtcpcc->state.rate;
	flow = mflow->flows;
	while (flow) {
		if (flow->downthreshmult >= 0.0) { /* if enabled */
			newfrate = newrate*cms_query_share(mflow->sched,flow);
			if (newfrate < flow->downthreshmult*flow->lastrate ||
			    newfrate > flow->upthreshmult*flow->lastrate) {
				flow->lastrate = newfrate;
				flow->ratechange = 1;
				if (flow->do_callback) 
					cmapp_send_wakeup(flow);
			}
		}
		flow = flow->next;
	}
}






















